package mo.offer_special;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

public class L075 {

    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> sortMap = new HashMap<>();
        for (int i = 0; i < arr2.length; i++) {
            sortMap.put(arr2[i], i);
        }
        int n = arr2.length;
        return Arrays.stream(arr1).boxed().sorted(Comparator.comparingInt(e -> sortMap.getOrDefault(e, n + e)))
                .mapToInt(Integer::intValue).toArray();
    }

    public int[] relativeSortArray2(int[] arr1, int[] arr2) {
        if(arr1.length <= 1)return arr1;
        // 1、创建一个大小为1001的数组
        int[] counts = new int[1001];
        // 2、遍历arr1，对arr1中的元素进行计数
        for(int num:arr1){
            counts[num]++;
        }
        // 3、遍历arr2，对重复元素进行arr1的填充
        int i = 0; // i代表arr1的当前空元素位置
        for(int num:arr2){
            while(counts[num] > 0){
                arr1[i] = num;
                i++;
                counts[num]--;
            }
        }
        // 4、将剩下的非重叠元素进行填充
        for(int num = 0;num < counts.length;num++){
            while(counts[num] > 0){
                arr1[i] = num;
                i++;
                counts[num]--;
            }
        }
        return arr1;
    }

}
